导语
决策树是一种基本的分类与回归方法。很多高级一点机器方法都用到了决策树，而且决策树很直观容易理解，很适合初学者入门。但是正是因为容易理解，反而容易忽视其背后的统计学概率论等算法基础。因此此篇就总结并讲解了分类决策树的特征选择依据和构建和3种常见决策树的异同。希望读者阅读后对决策树有更深入的数学理解。
解决的问题
- 有哪些决策树？
- 各种决策树的决策依据是什么？
- 信息增益和信息增益比的区别是什么？
- 各种决策树的优缺点？
- 决策树的适用范围有哪些？
- 哪些措施防止过拟合？
直观理解
决策树学习的目的就是构建一个树。决策树分类规则类似if-then，即基于一定的规则，不断地将数据分类下去。
下面是一个很经典的数据集，记录了14天的天气情况以及一个人(暂且叫ta小明)去没去打高尔夫，左边表格蓝色4栏表示各种天气条件，右边红色栏表示去没去打高尔夫。 我们通过观察发现， 只要天气是多云(overcast)时，小明就去打高尔夫；又或者碰到下雨天且湿度很大的时候小明就不去打高尔夫。这样我们就得到决策树的两条枝线： 多云 -> 去；下雨 -> 湿度高 ->不去。最终通过类似的选择，构建了一整颗决策树。有了这颗决策树后，看看天气预报我们就可以根据决策树预测小明以后去没去打高尔夫了。
另外，这里有个非常漂亮的决策树可视化讲解，十分推荐
现实问题
我们希望决策树可以很好的预测小明的行为。然而现实问题是我们怎么确定选择哪一个作为初始的判断依据呢？先选择有没有风再选择温度高低还是先选择温度高低再基于温度高低选择有没有风？……
随着慢慢地深入，更多的问题展现了出来：
面对有很多特征的数据集，我们依据哪种特征将数据分类？
其次如何建立一颗树？即我们如何基于特征选择的结果构建整个树？
最后我们得到整个树后，希望它不单在训练集上有很高的准确率，也希望在出现新数据后也有很好的预测能力。 然而这个树基本被完全分类，即每个样本几乎都被分到了正确的类别上，准确率接近100%。必然会出现过拟合overfitting。那么决策树如何避免过拟合呢？
以上3个问题，分别就对应着3个解决方法
- 特征选择
- 树的构建
- 树的剪枝
除算法本身构建问题之外，现实中数据集还会有数据缺失情况或者数据为数值型的情况，相关的解决方法读者可自行参阅参考链接7和8。
特征选择
不同决策树的算法最核心的不同就在于$if-then$ 选择时条件不同，其中最早的ID3算法(1983, Quinlan) 选用信息增益，其后改进型C4.5(1993, Quinlan)选用信息增益比，而由Breiman等人在1984年提出的CART算法采用基尼指数。
在介绍3种特征选择依据之前，先让我们了解下熵和条件熵的概念。
熵Entropy
定义
熵的概念最早起源于物理学，用于度量一个热力学系统的无序程度。在信息论和统计学中，熵表示随机变量不确定性的度量。
假$X$是一个有限个数的离散随机变量，其概率分布为：
随机事件$x_i$ 的信息定义为
熵其实是信息的期望，随机变量$X$的熵定义为：
其中$b$ 为2或$e$ 时，单位分别称作bit和nat
由定义可知熵只依赖于$X$的分布而与$X$的取值无关
实例
现在用抛硬币的例子直观的看熵代表的含义
假设抛一枚硬币，其头部向上表示为1，概率为p；头部向下表示为0，概率为q = 1-p，则熵计算为
当p取不同值时，得到熵如图所示曲线
可以看出，当p=0.5，即硬币头部向上的概率为0.5时，熵达到最大，对结果预测的准确性越小。而当p=1时，即每次抛硬币总是头部向上时，熵等于0，这时结果完全没有不确定性。
在高尔夫的例子中，打高尔夫的熵计算为
条件熵Conditional Entropy
定义
概率中有条件概率，熵同样有条件熵。
条件熵$H(Y|X)$表示在已知X的条件下随机变量Y的不确定性，定义为
实例
例如在高尔夫例子中在已知天气的情况下打高尔夫的条件是：
信息增益Information Gain
定义
在了解了熵和条件熵之后，我们就可以定义信息增益了。特征A对训练集D的信息增益$Gain(D,A)$ 定义为集合D的熵H(D)与特征A给定条件下D的条件熵$H(D|A)$ 之差，即
信息增益就表示由于特征A而使得数据集D的分类的不确定性减少的程度。对于不同的特征往往有不同的信息增益，信息增益大的特征则具有更强的分类能力。
实例
因此在高尔夫例子中，给定天气特征条件下，信息增益为
信息增益比Information Gain Ratio
定义
特征A对训练集D信息增益比$Gain_R(D,A)$定义为其信息增益$Gain(D,A)$与训练集D关于特征A的值的熵$H_A(D)$之比，即
其中
叫做本征信息Intrinsic information, 用于”惩罚“分支数目。当本征信息增大时，该特征的重要性也就降低了。
实例
信息增益看似已经足够了，为什么还要定义信息增益比？
那是因为信息增益存在偏向于选择取值较多的特征的问题。
如上图所示，假设我们在原数据集加上Day日期这个特征，我们来计算下信息增益$Gain(PlayGolf, Day)$
因为所有日期均只出现一次，给定每个日期后打高尔夫的结果只有yes或者no，所以条件熵可得
即给定日期下条件熵
$H(Playgolf| Day ) = 0$
所以
在所有特征中最高！但是我们肯定不会选择没有任何特殊分布的日期作为分类准则，信息增益也就失效了。除了日期外，常见容易影响信息增益的的特征还有身份证号，姓名，手机等特征。
计算所有后得到下表
| OutLook | Temperatrue |
|---|---|
| Gain:0.940-0.693 = 0.247 | Gain:0.940-0.911 = 0.029 |
| Gain ratio: 0.245/1.577 = 0.157 | Gain ratio:0.029/1.557 = 0.019 |
| Humidity | Windy |
|---|---|
| Gain:0.940-0.788 = 0.152 | Gain:0.940-0.911 = 0.029 |
| Gain ratio: 0.152/1.000 = 0.152 | Gain ratio:0.048/0.985 = 0.049 |
| Day |
|---|
| Gain: 0 |
| Gain ratio:0.940/3.807 = 0.246 |
可以看出Outlook的在原有的四类中信息增益比依旧是最高的，但是尽管运用信息增益比，Day的信息增益比最高。算法修改思路是先只考虑大于平均信息增益的特征，然后再根据信息增益比比较这些特征。
基尼指数 Gini Index
基尼指数和熵，信息增益等都没有公式上的关联，但是效果和熵类似。
定义
分类问题中，假设有K个类，样本点属于第k类的概率为$p_k$ ，则概率分布的基尼指数定义为
对于给定的样本集合D，其基尼指数为
其中，$D_k$ 是D中属于k类的样本子集。
如果样本集合D根据特征A是否可能取某一可能值a被分割成$D_1$ 和$D_2$两部分，即
在特征A的条件下，集合的D的基尼指数定义为
和熵类似，基尼指数$Gini(D)$表示集合D的不确定性，基尼指数$Gini(D,A)$表示经$A=a$分割后集合D的不确定性，即基尼指数值越大，样本集合的不确定性也就越大。
如上图所示，熵达到峰值的过程要相对慢一些，因此熵对于很混乱的集合的“判罚”往往要更重一些。
实例
继续看高尔夫的例子，共有9次yes和5次no，因此基尼指数计算为
算法构建
三种算法中，ID3和C4.5是一脉相承的，唯一的区别在于ID3采用信息增益准则选择特征，而C4.5选用信息增益比。CART分类决策树采用基尼指数，构建略简单一些，为二叉树。三种树均为Top-down模式，即从根节点贪心递归地构建，直至整个树“完全生长”。
另外要注意的点是决策树$if-then$ 的规则集合的一个性质：互斥并且完备，即每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或者一条规则所覆盖。
ID3和C4.5
输入：训练数据集D，特征集A，阈值e
- 若D中所有实例均属于同一类k，则T为单结点树，则将类k作为该节点的类标记，返回T
- 若A非空，则T为单结点树，则将D中实例数最大的类k作为该节点的类标记，返回T
- 否则，计算$A$中各特征对D的信息增益(比)，选择信息增益(比)最大的特征$A_g$
- 如果$A_g$ 小于阈值e，则置T为单结点树，将D中实例数最大的类k作为该节点的类标记
- 否则，对$A_g$ 的每一个值$a_i$ ，依$A_g = a_i$ 将D分割成若干个非空子集$D_i$ ,将$D_i$ 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成的树T，返回T
- 对第$i$ 个子结点，以$D_i$ 为训练集，以$A-{A_g}$ 为特征集，递归调用1-5步，得到子树 $T_i$ ，返回$T_i$
CART
输入：训练数据集D，停止计算的条件
- 计算现有特征对D的基尼指数。对每个特征A=a，根据样本点对A=a的测试为“是”或“否”将D分割成两个部分，计算A=a时的基尼指数
- 在所有可能的特征A以及所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征和最优切分点。将训练集依特征分配到两个子结点去
- 对两个子结点递归调用1，2，直至满足停止条件
停止条件可以时结点的样本个数小于阈值，或者基尼指数小于阈值，或者没有更多特征。
剪枝Pruning
上述的决策树生成方法均只考虑了局部子树的信息增益／信息增益比最优，但是对整体而言未必是最好的结果。这决策树往往对训练集拟合的很好，但是没有很好的泛化能力，也容易受到噪声noise和outlier的影响。为了防止过拟合，决策树有种方法叫做剪枝，即剪掉一部分枝叶以简化决策树，从而得到更好的泛化能力。
剪枝又可分为两种，一种叫前剪枝Prepruning，另一种叫后剪枝Postpruning。前剪枝就是在树生成时便规定一个阈值，低于阈值时便不再生长。其实已经运用在了上述算法构建中(阈值和停止条件）。缺点在于不容易找到一个合适的阈值。后剪枝则是在树完全生长后，我们通过剪枝算法，剪掉一部分枝叶。
下面重点讲解后剪枝。
后剪枝的核心思想便是：如果剪掉一个子树(合并其枝叶)可以使总的损失函数减小，则将其剪掉。
接下来我们构造一个简单的损失函数$C_{\alpha}(T)$
假设决策树T的有$|T|$ 个叶结点，表示模型的复杂度，在叶结点$t$有$N_t$个样本点，$H_t$叶结点上的熵，$\alpha\ge 0$为参数，定义决策树的损失函数为：
$\alpha$ 在式中控制预测误差和模型复杂度的影响，较大的促使选择较简单的模型，较小的促使是选择较复杂的模型，需要事先确定。
具体实施时通过计算每个结点的熵递归地向上回缩，如果回缩后(剪掉)损失函数变小了，则进行剪枝。
优缺点
优点
- 易于理解与解释，易可视化
- 不怎么需要数据预处理
- 用树预测数据时计算复杂度为$O(log n)$，很快
- 均可用于处理数值型和标类型数据
- 可用于需要多输出的问题
- 属于白箱模型，结果易解释。(反例：黑箱模型-神经网络(ANN)，结果不易解释)
缺点
- 容易建造过复杂的树，从而过拟合。
- 不稳定，对噪声和outlier的鲁棒性不高。可通过ensemble解决
- 构建最优决策树是NP问题，一般采用启发式方法，然而各个结点的局部最优不能保证全局最优
- 有一些问题很难用决策树学习。比如异或问题XOR，parity和multiplexer（后面两个不太会翻译）
- 如果一些类占绝定性（dominate）的比例，则决策树会造成偏差(bias)。推荐在用决策树学习之前平衡下数据集
结语
决策树易于解释的优点同样也是它的缺陷之一，即决策树最适合用来处理的是那些带分界点的，由大量分类数据和数值数据共同组成的数据集。如果对决策过程理解至关重要，那么采用决策树就在合适不过。
References
Trevor Hastie, Robert Tibshirani, Jerome Friedman The Elements of Statistical Learning
李航 《统计学习方法》
Peter Harrington《机器学习实战》
-